# 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 
# 
#  
# 
#  示例 1： 
# 
#  
# 
#  
# 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
# 输出：6
# 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 
#  
# 
#  示例 2： 
# 
#  
# 输入：height = [4,2,0,3,2,5]
# 输出：9
#  
# 
#  
# 
#  提示： 
# 
#  
#  n == height.length 
#  1 <= n <= 2 * 10⁴ 
#  0 <= height[i] <= 10⁵ 
#  
# 
#  Related Topics 栈 数组 双指针 动态规划 单调栈 👍 5474 👎 0
from typing import List


# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def trap(self, height: List[int]) -> int:
        # l = len(height)
        # left = [0] * l
        # right = [0] * l
        # volume = 0
        # # 动态规划
        # left[0] = height[0]
        # for i in range(1, l):
        #     # 此处用了动态规划的思想，例如前两个柱子里最高的为x，那么对于第三个柱子，就只用和x比较大小即可
        #     left[i] = max(height[i], left[i - 1])
        #
        # right[-1] = height[-1]
        # for j in range(l - 2, -1, -1):
        #     right[j] = max(height[j], right[j + 1])
        #
        # for i in range(l):
        #     temp = min(left[i], right[i]) - height[i]
        #     if temp >= 0:
        #         volume += temp
        # return volume
        stack = []
        water = 0
        for i in range(len(height)):
            while stack and height[i] > height[stack[-1]]:
                top = stack.pop()
                if not stack:
                    break
                width = i - stack[-1] - 1
                height_diff = min(height[i], height[stack[-1]]) - height[top]
                water += width * height_diff
            stack.append(i)
        return water


# leetcode submit region end(Prohibit modification and deletion)
print(Solution().trap(height=[0,1,0,2,1,0,1,3,2,1,2,1]))
